#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for (int i = 0; i < n; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int target = -nums[i];
            int right = n - 1;
            for (int left = i + 1; left < n; ++left)
            {
                if (left > i + 1 && nums[left] == nums[left - 1]) continue;
                while (left<right && nums[left] + nums[right]>target) --right;
                if (left == right) break;
                if (nums[left] + nums[right] == target) ans.push_back({ nums[i],nums[left],nums[right] });
            }
        }
        return ans;
    }

    int maxanswer(string& answerKey, int k, char ch)
    {
        int cnt = 0;
        for (int left = 0, right = 0; right < answerKey.size(); ++right)
        {
            if (answerKey[right] != ch) --k;
            while (k < 0)
            {
                k += answerKey[left++] != ch;
            }
            cnt = max(cnt, right - left + 1);
        }
        return cnt;
    }

    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(maxanswer(answerKey, k, 'T'), maxanswer(answerKey, k, 'F'));
    }
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> fdp(n, 0);
        vector<int> gdp(n, 0);
        for (int i = 1; i < n; ++i)
        {
            fdp[i] = fdp[i - 1] + nums[i - 1];
        }
        for (int i = n - 2; i >= 0; --i)
        {
            gdp[i] = gdp[i + 1] + nums[i + 1];
        }
        for (int i = 0; i < n; ++i)
        {
            if (fdp[i] == gdp[i]) return i;
        }
        return -1;
    }
};